package DataStructure.arrayAndList.findValue;

import Top100.GetMostValueofOrderArray;
import Logic.constant.C;

/**
 * @author liujun
 * @version 1.0
 * @date 2020/8/20
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 旋转数组的最值
 * 一个有序数组，比如[1,2,3,4,5,6,7],后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的最大值
 * 一个有序数组，比如[1,2,3,4,5,6,7],后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的最小值
 * 一个有序数组，比如[1,2,3,4,5,6,7],后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的给定值
 */

public class GetMostValueofOrderArrayImpl implements GetMostValueofOrderArray {
    @Override
    public int getMaxValue(int[] array) {
        if (array == null || array.length == 0) {
            return Integer.MIN_VALUE;
        }
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            if (left + 1 == right) {
                return Math.max(array[left], array[right]);
            }
            int mid = (left + right) / 2;
            // 最大值是跟左边对比，最小值是跟右边对比
            if (array[left] > array[mid]) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return array[right];
    }


    public int getMinValue(int[] array) {
        if (array == null || array.length == 0) {
            return Integer.MIN_VALUE;
        }
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            if (left + 1 == right) {
                return Math.min(array[left], array[right]);
            }
            int mid = (left + right) / 2;
            // 最大值是跟左边对比，最小值是跟右边对比
            if (array[right] < array[mid]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return array[left];
    }


    @Override
    public int getTargetValue(int[] array, int target) {

        if (array == null || array.length == 0) {
            return Integer.MIN_VALUE;
        }
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            //边界值
            /*if (array[left] == target) {
                return left;
            }
            if (array[right] == target) {
                return right;
            }*/
            // todo  为什么不可以使用left和right
            if (array[mid] == target) {
                return mid;
            }

            if (array[left] <= array[mid]) {
                if (array[left] <= target && target <= array[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (array[mid] <= target && target <= array[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return C.ErrorNum;
    }
}
